//你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row,
// col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你
//每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。 
//
// 一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。 
//
// 请你返回从左上角走到右下角的最小 体力消耗值 。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：heights = [[1,2,2],[3,8,2],[5,3,5]]
//输出：2
//解释：路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
//这条路径比路径 [1,2,2,2,5] 更优，因为另一条路径差值最大值为 3 。
// 
//
// 示例 2： 
//
// 
//
// 
//输入：heights = [[1,2,3],[3,8,4],[5,3,5]]
//输出：1
//解释：路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 ，比路径 [1,3,5,3,5] 更优。
// 
//
// 示例 3： 
//
// 
//输入：heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
//输出：0
//解释：上图所示路径不需要消耗任何体力。
// 
//
// 
//
// 提示： 
//
// 
// rows == heights.length 
// columns == heights[i].length 
// 1 <= rows, columns <= 100 
// 1 <= heights[i][j] <= 106 
// 
// Related Topics 深度优先搜索 并查集 图 二分查找 
// 👍 99 👎 0
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

class UnionFind {
public:
    vector<int> parent;
    vector<int> size;
    int n;
    int setCount;
public:
    UnionFind(int _n) : n (_n),setCount(_n),parent(_n),size(_n,1){
        iota(parent.begin(),parent.end(),0);
//        for (int i = 0; i < _n; ++i) {
//            parent[i] = i;
//        }
    }

    int findSet(int x){
        return parent[x] == x ? x : findSet(parent[x]);
    }

    bool uniteSet(int x ,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);
        if (x0 == y0){
            return false;
        }
        if (size[x0] < size[y0]){
            swap(x0,y0);
        }
        parent[y0] = x0;
        size[x0] += size[y0];
        --setCount;
        return true;
    }

    bool connected(int x,int y){
        int x0 = findSet(x);
        int y0 = findSet(y);

        return x0 == y0;
    }

};


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    int minimumEffortPath(vector<vector<int>>& heights) {
        int m = heights.size();
        int n = heights[0].size();

        vector<tuple<int,int,int>> edges;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                //将二维地址转换成一维
                int key = i*n+j;

                //计算边的权值
                if (i > 0){
                    edges.emplace_back(key - n , key , abs(heights[i][j]-heights[i-1][j]));
                }
                if (j > 0){
                    edges.emplace_back(key - 1 ,key , abs(heights[i][j]-heights[i][j-1]));
                }
            }
        }

        //边从小到大排序
        sort(edges.begin(),edges.end(),[](const auto& x,const auto& y){
            auto&& [x1,y1,z1] = x;
            auto&& [x2,y2,z2] = y;
            return z1 < z2;
        });

        //依次加入并查集
        UnionFind uf(m*n);
        int res = 0;

        for (const auto [x,y,z] :edges){
            uf.uniteSet(x,y);
            //如果左上角与右下角联通 则res = z；
            if (uf.connected(0,m * n -1)){
                res = z;
                break;
            }
        }
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)
